import java.util.HashMap;

/**
 * @author VernHe
 * @date 2021年07月27日 21:34
 */
public class Temp_06 {
    public static void main(String[] args) {
        System.out.println(getSubStr("abcabcbb"));
    }

    /**
     * 返回无重复最长子串
     *
     * @param str
     * @return
     */
    private static int getSubStr(String str) {
        /**
         * abcabcbb
         *
         *    0  1 2    3  4 5 6 7
         * [【a】 b c] 【a】 b c b b
         *
         * 比较【以前一个字符结尾的最长无重复子串的开始位置】和【当前字符上一次出现的位置】
         *
         */
        if (null == str) {
            return 0;
        }
        char[] chars = str.toCharArray();
        int len = chars.length;
        if (len < 0) {
            return 0;
        }


        // 定义dp数组，dp[i]表示以第i个字符结尾的最长无重复子串的长度
        int[] dp = new int[len + 1];
        // 定义map，保存字符上一次出现的Index，改进：用128为数组代替，ASCII值为下标
        HashMap<Character, Integer> map = new HashMap();
        // 初始化dp数组
        dp[0] = 0;
        dp[1] = 1;
        // 初始化第一个字符
        map.put(chars[0], 0);
        // 记录大长度
        int result = dp[1];

        // 循环
        for (int i = 2; i <= len; i++) {
            // 如果之前出线过，就比较位置
            if (map.containsKey(new Character(chars[i-1]))) {
                // i - dp[i - 1] 为以前一个字符结尾的不重复最长子串的起始位置
                if (map.get(new Character(chars[i-1])) <= i - dp[i - 1]) {
                    dp[i] = i - dp[i - 1];
                } else {
                    dp[i] = i - map.get(new Character(chars[i-1]));
                }
                // 更新最后一次出现的位置
                map.put(new Character(chars[i-1]),i);
            } else {
                // 第一次出现
                map.put(new Character(chars[i-1]), i);
                dp[i] = dp[i - 1] + 1;
            }
            dp[i] = Math.max(dp[i-1],dp[i]);
        }
        return dp[len];
    }
}
